package sorting

import "gitee.com/guuzaa/sorting/constraints"

func BucketSort[T constraints.Float](arr []T) []T {
	bucketSort(arr, len(arr))
	return arr
}

// ! T should <= 1.0 and >= 0.0
func bucketSort[T constraints.Float](arr []T, numBuckets int) {
	buckets := make([][]T, numBuckets)

	for i := 0; i < numBuckets; i++ {
		idx := int(T(numBuckets) * arr[i])
		buckets[idx] = append(buckets[idx], arr[i])
	}

	for i := 0; i < numBuckets; i++ {
		_ = BubbleSort(buckets[i])
	}

	idx := 0
	for i := 0; i < numBuckets; i++ {
		for j := 0; j < len(buckets[i]); j++ {
			arr[idx] = buckets[i][j]
			idx++
		}
	}
}
